﻿//4. 寻找两个正序数组的中位数
//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//算法的时间复杂度应该为 O(log(m + n)) 。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        if (nums1.size() > nums2.size())
        {
            swap(nums1, nums2);
        }
        int m = nums1.size();
        int n = nums2.size();
        nums1.insert(nums1.begin(), INT_MIN);
        nums2.insert(nums2.begin(), INT_MIN);
        nums1.push_back(INT_MAX);
        nums2.push_back(INT_MAX);
        //枚举nums1 i+j=(m+n+1)/2;   
        int i = 0, j = (m + n + 1) / 2;
        while (true)
        {
            //a[i] b[j] 是分割线左边的值 
            if (nums1[i] <= nums2[j + 1] && nums1[i + 1] > nums2[j])
            {
                int max1 = max(nums1[i], nums2[j]);
                int min2 = min(nums1[i + 1], nums2[j + 1]);
                //奇数中位数在 分割线左边 偶数分割线左右
                return (m + n) % 2 ? max1 : (max1 + min2) / 2.0;
            }
            i++;    //枚举
            j--;
        }
    }
};